package Algorithm.sort;

public abstract class MergeSort<T extends Comparable<T>>extends Sort<T> {

    protected T[] aux;//定义一个辅助数组,用于存放每次合并的子数组

    //归并方法
    public void merge(T[] nums,int l,int m,int h){//合并数组,参数l,m,h依次是数组的头指针,中间指针,尾指针,根据这三个参数划分数组前部分和后部分

        int i=l,j=m+1;//其中i是前半部分nums[l]的头指针,j是后半部分nums[m+1]的头指针

        //将需要合并的子数组数组传入辅助数组,其中k是合并数组的头指针,h是要合并数组的尾指针
        for(int k=l;k<=h;k++){
            aux[k]=nums[k];
        }
        //对合并的数组进行排序,其中k是合并数组的头指针,h是要合并数组的尾指针
        for(int k=l;k<=h;k++){
            if(i>m){
                nums[k]=aux[j++];
            }else if(j>h){
                nums[k]=aux[i++];
            }else if(aux[i].compareTo(aux[j])<=0){
                nums[k]=aux[i++];//保证排序稳定性
            }else {
                nums[k]=aux[j++];
            }
        }
    }
}
